/*
https://leetcode-cn.com/problems/minimum-time-to-finish-the-race/solution/jie-he-xing-zhi-qiao-miao-dp-by-endlessc-b963/
 */
import java.util.Arrays;

public class Solution2188 {
    public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
        int[] best=new int[25];
        Arrays.fill(best,Integer.MAX_VALUE);
        for (int[] tire : tires) {
            long t=tire[0];
            long r=tire[0];
            for (int i=1;i<20;i++){
                best[i]=Math.min((int)t,best[i]);
                r=r*tire[1];
                t=t+r;
                if (t>200000){
                    break;
                }
            }
        }
        int[] f=new int[numLaps+1];
        Arrays.fill(f,Integer.MAX_VALUE);
        f[0]=0;
        for (int i=1;i<=numLaps;i++){
            for (int j=i-1;j>Math.max(-1,i-20) && best[i-j]!=Integer.MAX_VALUE;j--){
                f[i]=Math.min(f[i],f[j]+changeTime+best[i-j]);
            }
        }
        return f[numLaps]-changeTime;
    }

    public static void main(String[] args) {
        System.out.println(new Solution2188().minimumFinishTime(new int[][]{{2,3},{3,4}},5,4));
    }
}
